package mo.offer_special;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class L015 {

    public List<Integer> findAnagrams(String s, String p) {
        if (p.length() > s.length()) {
            return Collections.emptyList();
        }
        List<Integer> res = new ArrayList<>();
        int[] p1 = new int[26];
        int[] s1 = new int[26];
        for (int i = 0; i < p.length(); i++) {
            p1[p.charAt(i)-'a']++;
            s1[s.charAt(i)-'a']++;
        }
        if (Arrays.equals(p1, s1)) {
            res.add(0);
        }
        int right = p.length();
        int left = 0;
        while (right < s.length()) {
            s1[s.charAt(right)-'a']++;
            s1[s.charAt(left)-'a']--;
            right++;
            left++;
            if (Arrays.equals(p1, s1)) {
                res.add(left);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        L015 test = new L015();
        System.out.println(test.findAnagrams("cbaebabacd", "abc"));
    }
}
